package com.leetcode.No0016;

import org.junit.Test;

import java.util.Arrays;

/**
 * @program: leetcode
 * @description: 最接近的三数之和
 * @author: wangzhihua
 * @date: 2021-12-23
 */
public class Solution02 {

	@Test
	public void test01() {
		int[] nums = new int[]{4,0,5,-5,3,3,0,-4,-5};
		int target = -2;
		System.out.println(threeSumClosest(nums, target));
	}

	public int threeSumClosest(int[] nums, int target) {
		Arrays.sort(nums);

		int result = 20000;
		int gap = 20000;

		int len = nums.length;
		for (int i = 0; i < len; ++i) {
			int x = i + 1;
			int y = len - 1;
			if (x >= y) {
				break;
			}

			while (x < y) {
				int sum = nums[i] + nums[x] + nums[y];
				if (sum == target) {
					return target;
				}
				if (sum > target) {
					--y;
				} else {
					++x;
				}
				if (gap > Math.abs(target - sum)) {
					gap = Math.abs(target - sum);
					result = sum;
				}
			}
		}

		return result;
	}

}
